package leetcode.t4LinkedList;


import java.util.concurrent.LinkedBlockingQueue;

/**
 * @author K
 * @date 2024/1/17 13:43
 */
public class LinkedListSolution {

    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next.next;
        while (fast != null&& fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(fast);

        ListNode dummy = new ListNode(-1);
        ListNode result = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                dummy.next = new ListNode(left.val);
                left = left.next;
            } else {
                dummy.next = new ListNode(right.val);
                right = right.next;
            }
            dummy = dummy.next;
        }

        dummy.next = left == null ? right : left;
        return result.next;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(4);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(1);
        ListNode listNode3 = new ListNode(3);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;


        ListNode h = listNode;
        ListNode first = h.next;
        h.next = h;
        listNode = first;
        int val = first.val;
        first.val = -1;

        LinkedBlockingQueue<Integer> queue = new LinkedBlockingQueue<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.poll();

        System.out.println();
    }
}
